//
// Created by 高森森 on 2022/2/16.
//

#ifndef LEETCODE_SOLUTION49_H
#define LEETCODE_SOLUTION49_H
#include<iostream>
using namespace std;
#include<vector>
#include <queue>

class Solution49 {
public:
    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
        vector<vector<int>> graph(n + 1);
        for (auto &e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }
        queue<int>q;
        q.push(1);
        //dist[n][0]表示从1点到n点的最短距离
        //dist[n][1]表示1点到n的次短距离
        vector<vector<int>>dist(n+1,vector<int>(2,INT_MAX));
        dist[1][0]=0;
        int step=0; //step为到达第节点的时间，ti+1=step+twait+time
        while(dist[n][1]==INT_MAX){
            int len=q.size();
            for(int i=0;i<len;i++){
                int node=q.front();
                q.pop();
                for(int neigh:graph[node]){
                    if(step+time<dist[neigh][0]){
                        dist[neigh][1]=dist[neigh][0];
                        dist[neigh][0]=step+time;
                        q.push(neigh);
                    }
                    else if(step+time>dist[neigh][0]&&step+time<dist[neigh][1]){
                        dist[neigh][1]=step+time;
                        q.push(neigh);
                    }
                }
            }
            step+=time;
            int light=step/change;
            step+=(light%2==1)?(light+1)*change-step:0;
        }
        return dist[n][1];
    }
};


#endif //LEETCODE_SOLUTION49_H
